GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Lineare Suche</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Lineare Suche</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Lineare Suche ist ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a>, der auch unter dem Namen sequentielle Suche bekannt ist. Er ist der einfachste <a href="Suchalgorithmus" class="mw-redirect" title="Suchalgorithmus">Suchalgorithmus</a> überhaupt.

Die Aufgabe besteht darin, ein Element in einer Liste oder einem <a href="Feld_(Datentyp)" class="mw-redirect" title="Feld (Datentyp)">Array</a> mit n Elementen zu finden.

Man geht dazu die Liste Element für Element durch, bis man es gefunden hat.

Der Suchaufwand wächst linear mit der Anzahl der Elemente in der Liste.

Die effizientere <a href="Bin%C3%A4re_Suche" title="Binäre Suche">Binäre Suche</a> kann nur bei geordneten Listen benutzt werden.

Für ungeordnete Listen existiert mit Lazy Select noch ein <a href="Randomisierter_Algorithmus" title="Randomisierter Algorithmus">randomisierter Algorithmus</a>, der mit relativ hoher Wahrscheinlichkeit das x-te Element einer Liste bezüglich einer Ordnung schneller als in linearer Zeit finden kann.

<div class="mw-heading mw-heading2"><h2 id="Komplexität">Komplexität</h2></div>

Die lineare Suche befindet sich in der <a href="Komplexit%C3%A4tsklasse" title="Komplexitätsklasse">Komplexitätsklasse</a> O(n), da sie im schlechtesten Fall (wenn der gesuchte Wert nicht gefunden werden kann) n Vergleiche benötigt.

Wenn die Daten zufallsverteilt sind, dann werden im <a href="Mittelwert" title="Mittelwert">Schnitt</a> (n+1)/2 Vergleichsoperationen benötigt.

Im besten Fall ist gleich das erste Element der Liste dasjenige, das man sucht.

Wenn die Anzahl der Elemente in einer Liste klein ist, dann ist es oft auch das effizienteste Verfahren.

<div class="mw-heading mw-heading2"><h2 id="Implementierungen_(Beispiele)">Implementierungen (Beispiele)</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Implementierung_in_Pseudocode">Implementierung in <a href="Pseudocode" title="Pseudocode">Pseudocode</a></h3></div>

<pre>BEGINN LinearSearch

</pre>

<pre> EINGABE: (S)uchschlüssel, (A)rray

</pre>

<pre> VARIABLE: N = Anzahl Elemente im Array 'A'

VARIABLE: SucheErfolgreich = falsch

VARIABLE: i = 0

</pre>

<pre> FÜR i BIS N ODER SucheErfolgreich

WENN A[i] = S

DANN SucheErfolgreich = wahr

</pre>

<pre> WENN SucheErfolgreich = wahr

DANN AUSGABE: i

SONST AUSGABE: Suche nicht erfolgreich

</pre>

<pre>ENDE

</pre>

<div class="mw-heading mw-heading3"><h3 id="Beispielimplementierung_in_Ruby">Beispielimplementierung in <a href="Ruby_(Programmiersprache)" title="Ruby (Programmiersprache)">Ruby</a></h3></div>

<div class="mw-highlight mw-highlight-lang-ruby mw-content-ltr" dir="ltr"><pre># Falls der Wert nicht gefunden wird, gibt die Methode nil zurück.

def lineare_suche(liste, gesucht)

liste.each_with_index do |wert, index|

return index if wert == gesucht

end

nil

end

# bzw.

liste.index(gesucht)

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Beispielimplementierung_in_Delphi_bzw._Free_Pascal">Beispielimplementierung in <a href="Embarcadero_Delphi" title="Embarcadero Delphi">Delphi</a> bzw. <a href="Free_Pascal" title="Free Pascal">Free Pascal</a></h3></div>

<div class="mw-highlight mw-highlight-lang-delphi mw-content-ltr" dir="ltr"><pre>// Durchsucht ein Array of Integer nach einem gesuchten Integer-Wert.

// Wird der gesuchte Wert gefunden, gibt die Funktion den Index des Wertes zurück.

// Falls der Wert nicht gefunden wird, gibt die Funktion -1 zurück.

function LineareSuche(gesucht : integer; ADaten : array of integer) : integer;

var

c : integer;

begin

Result := -1;

for c := Low(ADaten) to High(ADaten) do

if gesucht = ADaten[c] then

Result := c;

end;

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Beispielimplementierung_in_Objective_CAML">Beispielimplementierung in <a href="Objective_CAML" class="mw-redirect" title="Objective CAML">Objective CAML</a></h3></div>

<div class="mw-highlight mw-highlight-lang-ocaml mw-content-ltr" dir="ltr"><pre> let rec linsuche = function

([],a) -> false

| (x::t,a) -> if x = a then true else linsuche(t,a);;

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Beispielimplementierung_in_Java">Beispielimplementierung in <a href="Java_(Programmiersprache)" title="Java (Programmiersprache)">Java</a></h3></div>

Das Beispiel gibt den Wert <code>-1</code> zurück, wenn das gesuchte Element nicht im Array <code>daten</code> vorhanden ist. Ansonsten gibt es die Position des Elementes zurück.

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre>public static int lineareSuche(final int gesucht, final int[] daten) {

for (int i = 0; i < daten.length; i++) {

if (daten[i] == gesucht) {

return i;

}

return -1;

}

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Beispielimplementierung_in_Python">Beispielimplementierung in <a href="Python_(Programmiersprache)" title="Python (Programmiersprache)">Python</a></h3></div>

Findet alle Suchschlüssel in der Liste.

<div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre>def lineare_suche(liste, gesucht):

idxs = []

for index, element in enumerate(liste):

if element == gesucht:

idxs.append(index)

return idxs

# bzw.

lineare_suche = lambda l,g : [i for i,e in enumerate(l) if g == e]

</pre></div>

Findet erstes Vorkommen des Suchschlüssels in einer Liste.

if element == gesucht:

return index

# bzw. gibt es schon

lineare_suche = lambda l,g : l.index(g) if g in l else None

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Beispielimplementierung_in_C">Beispielimplementierung in <a href="C_(Programmiersprache)" title="C (Programmiersprache)">C</a></h3></div>

Findet ersten Suchschlüssel (Ganzzahl) in der Liste.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>#include <stdio.h>

/*

int*daten = Zeiger auf zu durchsuchende Daten

int datenlaenge = Größe des zu durchsuchenden "Arrays"

int suche = Gesuchte Ganzzahl

*/

int suche_sequenziell(int*daten, int datenlaenge, int suche) {

int i;

for (i=0;i<datenlaenge;i++)

if (daten[i]==suche)

return i;

return -1;

}

/* Beispielaufruf */

int main(void) {

int datenArray[10] = { 81, 1203, 180, 42, 10, 566, 102, 751, 54, 648 };

int pos = suche_sequenziell(datenArray, 10, 42);

/* -1 für nicht gefunden, ansonsten (erste) Position im Array, mit 0 beginnend */

if (pos<0)

printf("Nicht gefunden");

else

printf("Gefunden an Position %d",pos);

return 0;

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Liste_von_Algorithmen" title="Liste von Algorithmen">Liste von Algorithmen</a></li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2021-12-20" href="https://de.wikipedia.org/wiki/?title=Lineare_Suche&oldid=218374077">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>